package leetcode.code0911;

import leetcode.helper.HelpDebug;

public class TopVotedCandidate {

	private int[] leaders;
	private int[] notes;
	private int size;
	private int max;
	private int leader;
	private int[] times;
	private int LEN = 5000;

	public TopVotedCandidate(int[] persons, int[] times) {
		this.times = times;
		this.size = persons.length;
		this.leaders = new int[LEN];
		this.notes = new int[LEN];
		this.max = 0;
		this.leader = 0;
		for (int i = 0; i < size; i++) {
			int per = persons[i];
			int curNote = ++notes[per];
			if (curNote >= max) {//等号作用 - 最近获得投票的候选人将会获胜
				leader = per;
				max = curNote;
			}
			leaders[i] = leader;
		}
	}

	public int q(int t) {
		int L = 0;
		int R = size - 1;
		int ans = 0;
		while (L <= R) {
			int mid = ((R - L) >> 1) + L;
			int time = times[mid];
			if (time == t) {
				ans = leaders[mid];
				break;
			} else if (t > time) {
				ans = leaders[mid];
				L = mid + 1;
			} else {
				R = mid - 1;
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		TopVotedCandidate topVotedCandidate = new TopVotedCandidate(HelpDebug.str2array3("[0, 1, 1, 0, 0, 1, 0]"),
				HelpDebug.str2array3("[0, 5, 10, 15, 20, 25, 30]"));
		topVotedCandidate.q(3); // 返回 0 ，在时刻 3 ，票数分布为 [0] ，编号为 0 的候选人领先。
		topVotedCandidate.q(12); // 返回 1 ，在时刻 12 ，票数分布为 [0,1,1] ，编号为 1 的候选人领先。
		topVotedCandidate.q(25); // 返回 1 ，在时刻 25 ，票数分布为 [0,1,1,0,0,1] ，编号为 1 的候选人领先。（在平局的情况下，1 是最近获得投票的候选人）。
		topVotedCandidate.q(15); // 返回 0
		topVotedCandidate.q(24); // 返回 0
		topVotedCandidate.q(8); // 返回 1
	}

}
